import java.util.Stack; 
// 使用ArrayList 
// 而linkedList 是基于链表有 具有上述优点
class MinStack {
    Stack<Long> stack = new Stack<Long>();
    long min ;
    public void push(int x) {
        if(stack.isEmpty()){
            stack.add(0L);
            min = x;
        }else{    
            stack.add(x-min);  //所以每次在小于零的情况下，会出现min的变换
            if(x < min)
                min = x;
        }
    }

    public void pop() {
        if(!stack.isEmpty()){
            long tmp = stack.pop();
            if(tmp < 0) //在小于零的情况下，会出现min的变换
                min = -tmp + min; //重新更新最小值
        }
    }

    public int top() {
        if(!stack.isEmpty()){
            long tmp = stack.peek();
            if(tmp < 0)
                return (int)min;
            else
                return (int)(tmp + min);
        }
        else
            return -1;       
    }

    public int getMin() {
        return (int)min;      
    }
    // public static void main(String[] args) {
    //     MinStack s = new MinStack();
    //     for(int i=0; i<10; i++){
    //         s.push(i);
    //     }
    //     s.pop();
    //     s.push(-1);
    //     s.push(1);
    //     System.out.println(s.top());
    //     System.out.println(s.getMin());
    //     s.pop();
    //     s.pop();
    //     System.out.println(s.top());
    // }
}

//方法二 定义一个class保存
public class MinStack
{
    static class Element //定义了新的对象，但是这样会造成更多的space的浪费
    {
        final int value;
        final int min;
        Element(final int value, final int min)
        {
            this.value = value;
            this.min = min;
        }
    }
    final Stack<Element> stack = new Stack<>();

    public void push(int x) {
        final int min = (stack.empty()) ? x : Math.min(stack.peek().min, x);
        stack.push(new Element(x, min));
        
    }

    public void pop()
    {
        stack.pop();
    }

    public int top()
    {
        return stack.peek().value;
    }

    public int getMin()
    {
        return stack.peek().min;
    }

}